package com.hanxiaozhang.no10leetcode.tree;

import java.util.LinkedList;

/**
 * 〈一句话功能简述〉<br>
 * 〈给一棵二叉树，找到这棵树的最大深度〉
 * 示例：
 * 给定二叉树： [3,9,20,null,null,15,7]，
 * .    3
 * .   / \
 * .  9  20
 * .    /  \
 * .   15   7
 * 返回它的最大深度 3 。
 * <p>
 * 思路：方法1（自己的思路）  -> 使用递归
 * - 递归入参多传入上层层数。
 * - 递归的边界条件：node == null时，返回upperLevel。
 * - 每次递归 取 调用左右返回的值中，最大的。
 * <p>
 * 思路2：方法2（优秀的方法） -> 使用递归 -> 背下来
 * - 递归的边界条件：root == null时，返回0。
 * - 每次递归 Max(左孩子深度,右孩子深度) + 1
 *
 * @author hanxinghua
 * @create 2024/4/10
 * @since 1.0.0
 */
public class No104MaximumDepthBinaryTree {


    public static void main(String[] args) {

        TreeNode tree1 = new TreeNode(3);
        tree1.left = new TreeNode(9);
        tree1.right = new TreeNode(20);
        tree1.right.left = new TreeNode(15);
        tree1.right.right = new TreeNode(7);

        System.out.println(method1(tree1));
    }

    /**
     * 方法1：自己写的
     * 递归方法
     *
     * @param root
     * @return
     */
    private static Integer method1(TreeNode root) {

        return recursion(root, 0);
    }


    /**
     * @param node
     * @param upperLevel
     * @return
     */
    private static int recursion(TreeNode node, int upperLevel) {

        if (node == null) {
            return upperLevel;
        }

        int left = recursion(node.left, upperLevel + 1);

        int right = recursion(node.right, upperLevel + 1);

        return Math.max(left, right);
    }


    /**
     * 方法2
     * 优秀的方法
     *
     * @param root
     * @return
     */
    public int method2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(method2(root.left), method2(root.right)) + 1;
    }


}